package algorithms;

public class SerialMergeSort implements SortStrategy {
    private int[] data;
    private int[] ret;
    private int dataLength;

    public SerialMergeSort() {
        ;
    }

    public int[] sort(int[] data) {
        this.data = data.clone();
        this.ret = new int[data.length];
        this.dataLength = data.length;

        return divideAndMerge(0, this.dataLength-1);
    }

    private int[] divideAndMerge(int l, int r) {
        if (l==r) return new int[]{this.data[l]};
        int q = (l+r)/2;
        int[] left = divideAndMerge(l, q);
        int[] right = divideAndMerge(q+1, r);

        // 合并左右两个有序数组
        int[] retarr = new int[r-l+1];
        int index1=0, index2=0, index=0;
        for (; index1<left.length && index2<right.length; ){
            if (left[index1] <= right[index2]) {
                retarr[index] = left[index1];
                index++;
                index1++;
            } else {
                retarr[index] = right[index2];
                index++;
                index2++;
            }
        }
        if (index1 == left.length) {
            for (; index2<right.length; index2++, index++) retarr[index] = right[index2];
        } else {
            for (; index1<left.length; index1++, index++) retarr[index] = left[index1];
        }

        return retarr;
    }
}
